package interview;

import java.util.Stack;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description interview
 * @since JDK1.8
 *
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。
 * 最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SortStack {
    static class SortedStack {
        private final Stack<Integer> dataStack;
        private final Stack<Integer> tempStack;

        public SortedStack() {
            dataStack = new Stack<>();
            tempStack = new Stack<>();
        }

        public void push(int val) {
            if (isEmpty()) {
                dataStack.push(val);
            } else {
                while (!dataStack.isEmpty() && val > dataStack.peek()) {
                    tempStack.add(dataStack.pop());
                }
                dataStack.add(val);
                while (!tempStack.isEmpty()) {
                    dataStack.add(tempStack.pop());
                }
            }
        }

        public void pop() {
            if (isEmpty()) {
                return;
            }

            dataStack.pop();
        }

        public int peek() {
            return dataStack.peek();
        }

        public boolean isEmpty() {
            return dataStack.isEmpty();
        }
    }

    public static void main(String[] args) {
        SortedStack stack = new SortedStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());
    }
}
